// 从0开始，用vector直接从1开始就可以
template<class T>
struct RMQ {
	RMQ(vector<T> &v) {
		int n = v.size();
		int m = 31 - __builtin_clz(n);
		st_.resize(n);
		for (int i = 0; i < n; i++) {
			st_[i].resize(m + 1);
			st_[i][0] = v[i];
		}
		for (int i = 1; i <= m; i++) {
			int offset = 1 << (i - 1);
			for (int j = 0; j + offset < n; j++) {
				st_[j][i] = st_[j][i - 1] + st_[j + offset][i - 1];
			}
		}
	}

	T query(int l, int r) {
		assert(l <= r);
		int offset = 31 - __builtin_clz(r - l + 1);
		return st_[l][offset] + st_[r - (1 << offset) + 1][offset];
	}
	vector<vector<T>> st_;
};
struct Info {
	int val_;
	Info() {
		val_ = -2e9;
	}
};
Info operator+(const Info &lhs, const Info &rhs) {
	Info t;
	t.val_ = max(lhs.val_, rhs.val_);
	return t;
}